// ITI 1120 Fall 2006, Lab 8, Exercise 3
// Name: Diana Inkpen, Student# 123456

import java.util.Scanner;

/**
 * This program uses Euclid's algorithm to find the greatest
 * common divisor (GCD) of two integers.
 */

class Euclid
{
    public static void main (String[] args)
    {
        // SET UP KEYBOARD INPUT
        
        Scanner keyboard = new Scanner( System.in );

        // DECLARE VARIABLES/DATA DICTIONARY 

        int value1;     // one of the integers to find GCD
        int value2;     // second integer for GCD
        int result;     // GCD of value1 and value2

        // PRINT OUT IDENTIFICATION INFORMATION
        
        System.out.println();
        System.out.println("ITI 1120 Fall 2006, Lab 8, Exercise 3");
        System.out.println("Name: Diana Inkpen, Student# 123456");
        System.out.println();


        // READ IN GIVENS

        System.out.println( "Enter integer 1: " );
        value1 = keyboard.nextInt( );
        
        System.out.println( "Enter integer 2: " );
        value2 = keyboard.nextInt( );
        
        // BODY OF ALGORITHM

        result = findGCD( value1, value2 );

        // PRINT OUT RESULTS AND MODIFIEDS

        System.out.print( "The GCD of " + value1 + " and " );
        System.out.println( value2 + " is " + result );

    }

    // If the 'main' method calls other algorithms, put the method(s) below.

    /**
     * Determines the greatest common divisor (GCD) of a and b
     * using Euclid's algorithm.
     */

    public static int findGCD( int a, int b )
    {
        // DECLARE VARIABLES/DATA DICTIONARY

        int gcd;    // RESULT:  the GCD of a and b
        int m;  // Intermediate - maximum of a and b
        int n;  // Intermediate - minimum of a and b
        int partialRes;  // intermediate partial result

        // BODY OF ALGORITHM
        m = max(a,b);
        n = a + b - m;
        if ( m % n == 0 )
        {
            gcd = n;
        }
        else
        {
            gcd = findGCD( m, m%n );
        }

        // RETURN RESULT

        return gcd;
    }
    
    // Method max
    // Givens:  x and y - 2 integers
    static int max(int x, int y)
    {
      // Results
      int m; // maximum of x and y
      if(x > y)
      {
        m = x;
      }
      else
      {
        m = y;
      }
      return(m);
    }
    
}